#include <iostream>
#include <limits>

using namespace std;

// 邻接矩阵
template <typename V, typename E, int M = 10>
struct AMGraph
{
    V vexs[M];
    E arcs[M][M];
    int vexnum;
};

// 迪杰斯特拉算法
// 求图 G 中顶点 v 到其他各顶点的最短路径
// Dijkstra(G, v, P[], D[])
// P[] 保存最短路径上的前驱顶点
// D[] 最短路径长度
template <typename V, typename E, int M>
void Dijkstra(const AMGraph<V, E, M> &G, int v, int P[], E D[])
{
    const E INFINITY = std::numeric_limits<E>::max();
    bool finish[M]; // 是否已求得最短路径
    // 初始化最短路径(顶点 v 到其他各顶点的直接弧)
    for (int w = 0; w < G.vexnum; w++)
    {
        finish[w] = false;
        D[w] = G.arcs[v][w]; // 用弧的权值初始化
        P[w] = G.arcs[v][w] != INFINITY ? v : -1;
    }

    // 初始化起点信息
    D[v] = 0;
    P[v] = -1;
    finish[v] = true;

    // 求得 v 到其他各顶点的最短路径
    for (int i = 1; i < G.vexnum; i++)
    {
        // 找出未求得最短路径的顶点中路径长度最短的顶点 u
        auto min = INFINITY;
        int u = -1;
        for (int w = 0; w < G.vexnum; w++)
        {
            if (!finish[w] && D[w] < min)
            {
                min = D[w];
                u = w;
            }
        }
        // 得到 v 到 u 的最短路径
        finish[u] = true;
        // 更新 u 的邻接点的最短路径
        for (int w = 0; w < G.vexnum; w++)
        {
            if (G.arcs[u][w] != INFINITY && !finish[w] && min + G.arcs[u][w] < D[w])
            {
                D[w] = min + G.arcs[u][w];
                P[w] = u;
            }
        }
    }
}

int main()
{
    // 建立图
    const int N = 6;
    const int X = numeric_limits<int>::max();
    AMGraph<char, int> G{
        {'A', 'B', 'C', 'D', 'E', 'F'},
        {
            {0, 8, 2, X, X, 6},
            {8, 0, 4, X, 3, X},
            {2, 4, 0, 6, X, 3},
            {X, X, 6, 0, 1, 2},
            {X, 3, X, 1, 0, 5},
            {6, X, 3, 2, 5, 0},
        },
        N,
    };

    // 求 A 到其他各顶点的最短路径
    int P[N];
    int D[N];

    Dijkstra(G, 0, P, D);

    // 输出求得的最短路径
    for (int i = 0; i < N; i++)
    {
        cout << G.vexs[0] << "->" << G.vexs[i] << ":";
        if (D[i] < X)
        {
            cout << D[i];
            // 打印最短路径
            cout << ' ' << G.vexs[i];
            for (int j = P[i]; j != -1; j = P[j])
            {
                cout << "<-" << G.vexs[j];
            }
            cout << endl;
        }
        else
        {
            cout << "No path" << endl;
        }
    }
    return 0;
}